// 347. 前 K 个高频元素
// 给你一个整数数组 nums 和一个整数 k ，请你返回其中出现频率前 k 高的元素。
// 你可以按 任意顺序 返回答案。
// 输入: nums = [1,1,1,2,2,3], k = 2
// 输出: [1,2]
// 解法一：(不理解)
// 遍历数据，统计每个元素的频率，并将元素值（ key ）与出现的频率（ value ）保存到 map 中
// 遍历 map ，将前 k 个数，构造一个小顶堆
// 从 k 位开始，继续遍历 map ，每一个数据出现频率都和小顶堆的堆顶元素出现频率进行比较，
// 如果小于堆顶元素，则不做任何处理，继续遍历下一元素；如果大于堆顶元素，
// 则将这个元素替换掉堆顶元素，然后再堆化成一个小顶堆。
// 遍历完成后，堆中的数据就是前 k 大的数据


let topKFrequent = function(nums, k) {
    let map = new Map(), heap = [,]
    nums.map((num) => {
        if(map.has(num)) map.set(num, map.get(num)+1)
        else map.set(num, 1)
    })
    
    // 如果元素数量小于等于 k
    if(map.size <= k) {
        return [...map.keys()]
    }
    
    // 如果元素数量大于 k，遍历map，构建小顶堆
    let i = 0
    map.forEach((value, key) => {
        if(i < k) {
            // 取前k个建堆, 插入堆
            heap.push(key)
            // 原地建立前 k 堆
            if(i === k-1) buildHeap(heap, map, k)
        } else if(map.get(heap[1]) < value) {
            // 替换并堆化
            heap[1] = key
            // 自上而下式堆化第一个元素
            heapify(heap, map, k, 1)
        }
        i++
    })
    // 删除heap中第一个元素
    heap.shift()
    return heap
};

// 原地建堆，从后往前，自上而下式建小顶堆
let buildHeap = (heap, map, k) => {
    if(k === 1) return
    // 从最后一个非叶子节点开始，自上而下式堆化
    for(let i = Math.floor(k/2); i>=1 ; i--) {
        heapify(heap, map, k, i)
    }
}

// 堆化
let heapify = (heap, map, k, i) => {
    // 自上而下式堆化
    while(true) {
        let minIndex = i
        if(2*i <= k && map.get(heap[2*i]) < map.get(heap[i])) {
            minIndex = 2*i
        }
        if(2*i+1 <= k && map.get(heap[2*i+1]) < map.get(heap[minIndex])) {
            minIndex = 2*i+1
        }
        if(minIndex !== i) {
            swap(heap, i, minIndex)
            i = minIndex
        } else {
            break
        }
    }
}

// 交换
let swap = (arr, i , j) => {
    let temp = arr[i]
    arr[i] = arr[j]
    arr[j] = temp
}


// 解法二
let topKFrequent1 = function(nums, k) {
    let map = new Map(), arr = [...new Set(nums)]
    nums.map((num) => {
        if(map.has(num)) map.set(num, map.get(num)+1)
        else map.set(num, 1)
    })
    
    return arr.sort((a, b) => map.get(b) - map.get(a)).slice(0, k);
};


// 215. 数组中的第K个最大元素
// 给定整数数组 nums 和整数 k，请返回数组中第 k 个最大的元素。

// 请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。
// 输入: [3,2,1,5,6,4] 和 k = 2
// 输出: 5
// 思路：第一步构建初始堆：是自底向上构建，从最后一个非叶子节点开始。

// 第二步就是下沉操作让尾部元素与堆顶元素交换，最大值被放在数组末尾，并且缩小数组的length，
// 不参与后面大顶堆的调整

// 第三步就是调整：是从上到下，从左到右,因为堆顶元素下沉到末尾了，要重新调整这颗大顶堆

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number}
 */
// 整个流程就是上浮下沉
 var findKthLargest = function(nums, k) {
    let heapSize=nums.length;
    buildMaxHeap(nums,heapSize);// 构建好了一个大顶堆
    // 进行下沉 大顶堆是最大元素下沉到末尾
    for(let i=nums.length-1;i>=nums.length-k+1;i--){
        swap(nums,0,i);
        --heapSize;// 下沉后的元素不参与到大顶堆的调整
        // 重新调整大顶堆
        maxHeapify(nums,0,heapSize);
    }
    return nums[0];
    // 自下而上构建一颗大顶堆
    function buildMaxHeap(nums,headSize){
        for(let j=Math.floor(headSize/2)-1;j>=0;j--)
            maxHeapify(nums,j,headSize)
    }
    // 从左向右，自上而下的调整节点
    function maxHeapify(nums,i,headSize){
        let larget=i;
        let l=i*2+1;
        let r=i*2+2;
        if(l<headSize&&nums[l]>nums[larget]) {
            larget=l;
        }
        if(r<headSize&&nums[r]>nums[larget]){
            larget=r;
        }
        if(larget!==i){
            swap(nums,i,larget);// 进行节点调整
            // 继续调整下面的非叶子节点
            maxHeapify(nums,larget,headSize);
        }
    }
    function swap(a,i,larget){
        let temp=0;
        temp=a[i];
        a[i]=a[larget];
        a[larget]=temp;
    }
};